/**
 * @author ghp
 * @title
 */
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] sum = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            // 构建sum数组
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    if (j == 0) {
                        sum[i][j] = 1;
                    } else {
                        sum[i][j] += sum[i][j - 1] + 1;
                    }
                } else {
                    sum[i][j] = 0;
                }
                int width = sum[i][j];
                // 以当前节点为矩形的右下角，往上枚举
                for (int k = i; k >= 0; k--) {
                    int height = i - k + 1;
                    // 选所有行中的最小宽度作为当前矩形的宽度
                    width = Math.min(width, sum[k][j]);
                    // 更新最大矩形的面积
                    ans = Math.max(ans, height * width);
                }
            }
        }
        return ans;
    }
}